/*
 * @lc app=leetcode.cn id=872 lang=typescript
 *
 * [872] 叶子相似的树
 */

// @lc code=start

// Definition for a binary tree node.
/* class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
} */

function leafSimilar(root1: TreeNode | null, root2: TreeNode | null): boolean {
  const getLeafNodes = (root: TreeNode | null, result: number[]): void => {
    const stack = [];
    while (root || stack.length) {
      while (root) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      if (root.left === null && root.right === null) {
        result.push(root.val);
      }
      root = root.right;
    }
  };

  const isSameVal = (a: number[], b: number[]): boolean => {
    if (a.length !== b.length) return false;
    let i = 0,
      j = 0;
    while (i < a.length) {
      if (a[i++] !== b[j++]) return false;
    }
    return true;
  };

  const leafs1 = [];
  getLeafNodes(root1, leafs1);
  const leafs2 = [];
  getLeafNodes(root2, leafs2);
  return isSameVal(leafs1, leafs2);
}
// @lc code=end
